package com.lenl.arithmetic.tenusablealgorithm.floyd;

import java.util.Arrays;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-16 15:41
 * @description 弗洛伊德算法
 */
public class FloydAlgorithm {
    public static void main(String[] args) {
        char[] vertex={'A','B','C','D','E','F','G'};
        int[][] matrix=new int[vertex.length][vertex.length];
        final int N=65535;//标识不可链接
        matrix[0]=new int[]{0,5,7,N,N,N,2};
        matrix[1]=new int[]{5,0,N,9,N,N,3};
        matrix[2]=new int[]{7,N,0,N,8,N,N};
        matrix[3]=new int[]{N,9,N,0,N,4,N};
        matrix[4]=new int[]{N,N,8,N,0,5,4};
        matrix[5]=new int[]{N,N,N,4,5,0,6};
        matrix[6]=new int[]{2,3,N,N,4,6,0};
        //创建Graph对象
        Graph graph=new Graph(vertex.length,matrix,vertex);
        graph.floyd();
        graph.show();

    }
}

//创建图
class Graph{
    char[] vertex;//存放顶点的数组
    private int[][] dis;//保存各个顶点到其他顶点的距离，最后结果在该数组中
    private int[][] pre;//保存到达目标顶点的其他前驱顶点

    /**
     *
     * @param length 大小
     * @param matrix 初始邻接矩阵
     * @param vertex 顶点数组
     */
    public Graph(int length,int[][] matrix,char[] vertex){
        this.vertex=vertex;
        this.dis=matrix;
        this.pre=new int[length][length];
        //初始化pre,存放的是前驱顶点的下标
        for (int i=0;i<length;i++){
            Arrays.fill(pre[i],i);
        }
    }

    //显示pre和dis
    public  void  show(){
        char[] vertex={'A','B','C','D','E','F','G'};
        for (int k=0;k<dis.length;k++){
            //先将pre数组输出
            for (int i=0;i<dis.length;i++){
                System.out.print(vertex[ pre[k][i]]+" ");
            }
            System.out.println();
            for (int j=0;j<dis.length;j++){
                System.out.print("("+vertex[k]+"到"+vertex[j]+"的最短路径："+ dis[k][j]+")") ;
            }
            System.out.println();
        }
    }
    //弗洛伊德算法
    public  void floyd(){
        int len=0;
        //遍历每一个中间顶点
        for (int k=0;k<dis.length;k++){
            //每一个起始顶点
            for (int i=0;i<dis.length;i++){
                //结束顶点
                for (int j = 0; j < dis.length; j++) {
                    len=dis[i][k]+dis[k][j];
                    if(len<dis[i][j]){
                        dis[i][j]=len;
                        pre[i][j]=pre[k][j];
                    }
                }

            }
        }



    }


}
